package com.study.algorithm.base.list;

import com.google.common.collect.Lists;
import com.study.algorithm.base.common.ListUtil;

import java.util.List;

/**
 * MergeSort_SmallSum
 *
 * @author wanghuilong
 * @version 1.0
 * @description use merge sort  for small sum problem
 * @date 2023/1/24 23:03
 */
public class MergeSort_SmallSum {
    
    public static void main(String[] args) {
        List<Integer> list = ListUtil.getRandomList(10);
        int[] arr = new int[]{7,1,3,4,2,5,0};
//        System.out.println(process(arr,0,arr.length-1));
        printContraryOrderPair(arr,0,arr.length-1);
    }

    private static int process(int[] arr, int L, int R) {
        if(L == R) {
            return 0;
        }
        int mid = L + ((R - L) >> 1);
        return process(arr,L,mid) + process(arr,mid+1,R) + 
                merge(arr,L,mid,R);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int[] helper = new int[r - l + 1];
        int i = 0;
        int sum = 0;
        int p1 = l;
        int p2 = mid + 1;
        while(p1 <= mid && p2 <= r) {
            sum += arr[p1] < arr[p2] ? (r - p2 + 1)*arr[p1] : 0;
            helper[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= mid) {
            helper[i++] = arr[p1++];
        }
        while(p2 <= r) {
            helper[i++] = arr[p2++];
        }
        for (int j = 0; j < helper.length; j++) {
            arr[l+j] = helper[j];
        }
        return sum;
    }

    /**
     * print all the contrary order pair
     * contrary order pair: the left number is bigger than the right number
     * @param arr
     * @param L
     * @param R
     */
    public static  void  printContraryOrderPair(int[] arr, int L, int R) {
        if(L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        printContraryOrderPair(arr,L,mid);
        printContraryOrderPair(arr,mid+1,R);
        mergeContraryOrderPair(arr,L,mid,R);
    }

    private static void mergeContraryOrderPair(int[] arr, int l, int mid, int r) {
        int[] helper = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = mid + 1;
        while(p1 <= mid && p2 <= r) {
            if(arr[p1] > arr[p2]) {
                System.out.println(arr[p1]+","+arr[p2]);
                helper[i++] = arr[p2++];
            }else {
                helper[i++] = arr[p1++];
            }
        }
        while(p1 <= mid) {
            helper[i++] = arr[p1++];
        }
        while(p2 <= r) {
            helper[i++] = arr[p2++];
        }
        for (int j = 0; j < helper.length; j++) {
            arr[l+j] = helper[j];
        }
    }


}
